Integrated circuit layouts cannot be split into two masks if they include conflict cycles. A conflict cycle may be referred to as an odd cycle because it is a cycle in the conflict graph that contains an odd number of edges. Many layout designers (e.g., customers of a semiconductor foundry) do not have tools to check those conflict cycles and thus can violate the rules to split the layouts. Various layout approaches cannot fix an odd cycle and associated problems because of the constraint on the stitch locations. A straightforward method is to split the patterns, connect the polygons by stitch areas, and use a matrix global solver to decompose the layout. In that method, however, memory consumption is huge; cycle time increases; customer generally is not involved in the layout creation process; and the layout creation process is not user-friendly because different approaches are employed to decompose the layout when the polygons are cut and not cut.
Like reference symbols in the various drawings indicate like elements.